﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace encryption
{
    class Program
    {
        static void Main(string[] args)
        {
            new 测试().hash();
        }
    }
    public class 测试
    {
        public 测试()
        {

        }

        public void hash()
        {
            int[] position = new int[1024];
            int temp_length = 1024;
            Random ran = new Random();
            string key;
            StringBuilder str = new StringBuilder();
            int count;
            Int64 sum = 0;
            int atephobia = 0;
            str.Append("ap\r\n步长冲突数+1\r\n");  
            for (int i = 0; i < 1000; i++)
            {
                key = ranstr(ran.Next(1, 10), ran);
                count = hash(ref position, temp_length, key);
                if (count < 0)
                {
                    atephobia++;
                    str.Append("计算失败，计算" + -1 * count + "\r\n");
                }
                else
                {
                    sum += count;
                    str.Append("冲突" + count.ToString() + "\r\n");
                }
            }
            str.Append("平均冲突 " + sum / (1000 - atephobia));
            FileStream file = new FileStream("1.txt", FileMode.Append);
            byte[] buffer;
            buffer = Encoding.UTF8.GetBytes(str.ToString());
            file.Write(buffer, 0, buffer.Length);
            file.Flush();
            file.Close();
        }

        private string ranstr(int count, Random ran)
        {
            StringBuilder str = new StringBuilder();
            str.Clear();
            for (int i = 0; i < count; i++)
            {
                str.Append(Convert.ToChar(ran.Next() % 2 == 0 ? ran.Next(19968, 40864) : ran.Next(33, 126)));
            }
            return str.ToString();
        }

        private int hash(ref int[] position, int temp_length, string key)
        {
            bool[] exist = new bool[temp_length];
            int i;
            int temp;
            int count;//冲突数
            int sum;//总冲突数
            for (i = 0; i < temp_length; i++)
            {
                exist[i] = false;
            }

            if (position.Length != temp_length)
            {
                position = new int[temp_length];
            }
            //int a;
            //int b;
            //int c;
            //a = 6530;
            //b = 128;
            //c = 234576;
            sum = 0;           
            for (i = 0; i < temp_length; i++)
            {
                //temp = (int)(key[i % key.Length]) % temp_length;
                //temp = (int)((a * (key[i % key.Length] % b) + c) % temp_length);//除留
                //temp = (int)(rs(key, i) % temp_length);//rs
                //temp = (int)(js(key, i) % temp_length);//js
                //temp = (int)(pjw(key, i) % temp_length);//pjw
                //temp = (int)(elf(key, i) % temp_length);//elf
                //temp = (int)(bkdr(key, i) % temp_length);//bkdr
                //temp = (int)(sdbm(key, i) % temp_length);//sdbm
                //temp = (int)(djb(key, i) % temp_length);//djb
                temp = (int)(ap(key, i) % temp_length);//ap
                count = i / key.Length;
                while (exist[temp])
                {
                    temp = conflict(temp, i, count, key, temp_length);
                    count++;
                    sum++;
                    if (count > 10 * temp_length)
                    {
                        Debug.Write("冲突数过多" + i.ToString() + "\r\n");
                        return -1 * i;
                    }
                }
                position[i] = temp;
                exist[temp] = true;
            }
            Debug.Write("冲突数" + sum.ToString());
            return sum;
        }

        private long rs(string key, int i)
        {
            int b = 378551;
            int a = 63689;
            long hash = 0;
            key += i.ToString();
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            for (i = 0; i < str.Length; i++)
            {
                hash = hash * a + str[i];
                a = a * b;
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long js(string key, int i)
        {
            key += i.ToString();
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long hash = 1315423911;
            for (i = 0; i < str.Length; i++)
            {
                hash ^= ((hash << 5) + str[i] + (hash >> 2));
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long pjw(string key, int i)
        {
            //key = key + i.ToString();
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            int BitsInUnsignedInt = (4 * 8);
            int ThreeQuarters = (BitsInUnsignedInt * 3) / 4;
            int OneEighth = (BitsInUnsignedInt / 8);
            int HighBits = (int)((0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth));
            long hash = 0;
            long test = 0;
            for (i = 0; i < str.Length; i++)
            {
                hash = (hash << OneEighth) + str[i];
                if ((test = hash & HighBits) != 0)
                {
                    hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
                }
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long elf(string key, int i)
        {
            key += i.ToString();
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long hash = 0;
            long x = 0;
            for (i = 0; i < str.Length; i++)
            {
                hash = (hash << 4) + str[i];
                if ((x = hash & 0xF0000000L) != 0)
                {
                    hash ^= (x >> 24);
                }
                hash &= ~x;
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long bkdr(string key, int i)
        {
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long seed = 131;
            long hash = 0;
            for (i = 0; i < str.Length; i++)
            {
                hash = (hash * seed) + str[i];
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long sdbm(string key, int i)
        {
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long hash = 0;
            for ( i = 0; i < str.Length; i++)
            {
                hash = str[i] + (hash << 6) + (hash << 16) - hash;
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long djb(string key, int i)
        {
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long hash = 5381;
            for ( i = 0; i < str.Length; i++)
            {
                hash = ((hash << 5) + hash) + str[i];
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private long ap(string key, int i)
        {
            i = i % key.Length;
            string str = key.Substring(i) + key.Substring(0, i);
            long hash = 0xAAAAAAAA;
            for ( i = 0; i < str.Length; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ str[i] * (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) + str[i] ^ (hash >> 5)));
                }
            }
            if (hash < 0)
            {
                hash = hash * -1;
            }
            return hash;
        }

        private int conflict(int position, int i, int count, string key, int temp_length)
        {
            //int countconflict;
            //int sum;
            //i = i % key.Length;
            //sum = 0;
            //for (countconflict = 0; countconflict <= count; countconflict++)
            //{
            //    sum += key[i];
            //}
            //sum += key[i];
            //return sum % temp_length;
            return (position + count + 1) % temp_length;
        }

    }
}
